//给你一个链表数组，每个链表都已经按升序排列。 
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。 
//
// 
//
// 示例 1： 
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
// 
//
// 示例 2： 
//
// 输入：lists = []
//输出：[]
// 
//
// 示例 3： 
//
// 输入：lists = [[]]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// k == lists.length 
// 0 <= k <= 10^4 
// 0 <= lists[i].length <= 500 
// -10^4 <= lists[i][j] <= 10^4 
// lists[i] 按 升序 排列 
// lists[i].length 的总和不超过 10^4 
// 
// Related Topics 链表 分治 堆（优先队列） 归并排序 👍 1575 👎 0

package leetcode.editor.cn;


public class _23_MergeKSortedLists {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ListNode[] links = new ListNode[]{
//                createLink(new int[]{}),
                createLink(new int[]{1, 3, 4}),
                createLink(new int[]{2, 6}),
        };

        Solution solution = new _23_MergeKSortedLists().new Solution();
        ListNode res = solution.mergeKLists(links);
        show(res);
    }

    public static void show(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    public static ListNode createLink(int[] nums) {
        ListNode head = new ListNode(-1, null);
        ListNode pre = head;
        for (int i = 0; i < nums.length; i++) {
            pre.next = new ListNode(nums[i], null);
            pre = pre.next;
        }
        return head.next;
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            return merge(lists, 0, lists.length - 1);
        }

        private ListNode merge(ListNode[] lists, int left, int right) {
            if (left > right) {
                return null;
            } else if (left == right) {
                return lists[left];
            }
            int mid = left + (right - left) / 2;
            return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
        }

        public ListNode mergeKLists_2(ListNode[] lists) {
            for (int i = 1; i < lists.length; i++) {
                lists[0] = mergeTwoLists(lists[0], lists[i]);
            }
            return lists[0];
        }

        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode head = new ListNode(-1);
            ListNode pre = head;
            ListNode cur1 = l1;
            ListNode cur2 = l2;
            while (cur1 != null && cur2 != null) {
                if (cur1.val <= cur2.val) {
                    pre.next = cur1;
                    cur1 = cur1.next;
                } else {
                    pre.next = cur2;
                    cur2 = cur2.next;
                }
                pre = pre.next;
            }
            pre.next = cur1 == null ? cur2 : cur1;
            return head.next;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}